package fina.AC;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class AC {
    public static class Node{
        Node[] nexts;
        boolean endUse;
        String end;
        Node fail;
        public Node(){
            endUse = false;
            end = null;
            fail = null;
            nexts = new Node[26];
        }
    }
    public static class ACAutomation{
        public Node root;

        public ACAutomation() {
            this.root = new Node();
        }

        public  void insert(String s){
            char[] str = s.toCharArray();
            Node node = root;
            for (int i = 0; i < str.length; i++) {
                int next = str[i] - 'a';
                if(node.nexts[next] == null){
                    node.nexts[next] = new Node();
                }
                node = node.nexts[next];
            }
            node.end = s;
        }

        public void build(){
            Queue<Node> queue = new LinkedList<>();
            queue.add(root);
            Node cur = null;
            Node cfail = null;
            while(! queue.isEmpty()){
                cur = queue.poll();
                for (int i = 0; i < 26; i++) {
                    if(cur.nexts[i] != null){
                        cur.nexts[i].fail = root;
                        cfail = cur.fail;
                        while(cfail != null){
                            if(cfail.nexts[i] != null){
                                cur.nexts[i].fail = cfail.nexts[i];
                                break;
                            }
                            cfail = cfail.fail;
                        }
                        queue.add(cur.nexts[i]);
                    }
                }
            }
        }
        public List<String> containsWord(String context){
            Node cur = root;
            List<String> res = new ArrayList<>();
            Node follow = root;
            char[] str = context.toCharArray();
            for (int i = 0; i < str.length; i++) {
                int next = str[i] - 'a';
                while(cur.nexts[next] != null && cur != root){
                    cur = cur.fail;
                }
                cur = cur.nexts[next] == null ? cur.nexts[next] : root;
                follow = cur;
                while(follow != root){
                    if(follow.endUse){
                        break;
                    }
                    if(follow.end != null){
                        res.add(follow.end);
                        follow.endUse = true;
                    }

                    follow = follow.fail;
                }
            }
            return res;
        }
    }
    public static void main(String[] args) {
        ACAutomation ac = new ACAutomation();
        ac.insert("dhe");
        ac.insert("he");
        ac.insert("abcdheks");
        // 设置fail指针
        ac.build();

        List<String> contains = ac.containsWord("abcdhekskdjfafhasldkflskdjhwqaeruv");
        for (String word : contains) {
            System.out.println(word);
        }
    }

}
